package com.cty.twentySixthDay;
/*
给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。
*/
public class Q_40 {
    // 过了主包的算法过了 时间复杂度O(n) 空间复杂度O(n) 因为用到了栈
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        // 计算左子树 因为计算出的层数 - 1 是子树的路径长度 正好子树和根节点之间还有一段长度 所以就不用在加长度了
        int leftLength = diameterOfSubTree(root.left);
        int rightLength = diameterOfSubTree(root.right);
        // 计算出其左右子树的最大深度
        int subTreeLength = Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right));
        return Math.max(leftLength + rightLength,subTreeLength);
    }

    //计算子树的最长路径
    public int diameterOfSubTree(TreeNode root) {
        if (root == null) return 0;
        return Math.max(diameterOfSubTree(root.left),diameterOfSubTree(root.right)) + 1;
    }

    // 力扣官方题解 深度优先搜索
    /*
    * 思路：
    *   计算当前节点的最大深度
    *   其直径等于 左子节点的深度 + 右子节点的深度 - 1
    *   时间复杂度O(N) 空间复杂度O(Height) 也就是树的高度
    * */
    int ans = 0;
    public int diameterOfBinaryTree2(TreeNode root) {
        depth(root);
        // 最大的直径等于左右的最大深度
        return ans;
    }

    public int depth(TreeNode root) {
        if (root == null) return 0;
        int L = depth(root.left);
        int R = depth(root.right);
        // 计算出左右的深度计算复制即可
        ans = Math.max(L + R,ans);
        // 返回最大深度
        return Math.max(R,L) + 1;
    }
}
